package fireway;

/**
 * <p> 归并排序 </p>
 * 2018年 07月 03日 星期二
 *
 * @author fireway
 */
public class MergeSort {
    private static final boolean DEBUG = true;

    private int mDebugRecCount = 0;

    // refer to long array
    private long mLArray[];

    // number of data items
    private int mSize;

    public MergeSort(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public void insert(int value) {
        mLArray[mSize++] = value;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize -1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    public void mergeSort() {
        long[] workSpace = new long[mSize];
        recMergeSort(workSpace, 0, mSize - 1);
    }

    private String logPrefixOfRec(int count) {
        StringBuffer sb = new StringBuffer();
        while (count > 0) {
            sb.append("    ");
            count--;
        }
        return sb.toString();
    }

    private void recMergeSort(long[] workSpace, int left, int right) {
        if (DEBUG) {
            System.out.println(logPrefixOfRec(mDebugRecCount) + "Entering " + left + " ~ " + right);
            mDebugRecCount++;
        }

        if (left == right) {
            if (DEBUG) {
                System.out.println(logPrefixOfRec(mDebugRecCount) + "Base-Case Return " + left + " ~ " + right);
                mDebugRecCount--;
            }
            return;
        } else {
            int mid = (left + right) / 2;
            if (DEBUG) {
                System.out.println(logPrefixOfRec(mDebugRecCount) + "Will sort left half of " + left + " ~ " + mid);
            }
            recMergeSort(workSpace, left, mid);
            if (DEBUG) {
                System.out.println(logPrefixOfRec(mDebugRecCount) + "Will sort right half of " + (mid + 1) + " ~ " + right);
            }
            recMergeSort(workSpace, mid + 1, right);
            if (DEBUG) {
                System.out.println(logPrefixOfRec(mDebugRecCount) + "Will merge halves into " + left + " ~ " + right);
            }
            merge(workSpace, left, mid + 1, right);
            if (DEBUG) {
                mDebugRecCount--;
                System.out.println(logPrefixOfRec(mDebugRecCount) + "Return " + left + " ~ " + right);
            }
        }
    }

    /**
     * 将两个有序表合并和一个有序表
     *
     * @param workSpace
     * @param firstArrayLeft 第一个有序表的起始下标
     * @param secondArryLeft 第二个有序表的起始下标
     * @param secondArryRight 第二个有序表的结束下标
     */
    private void merge(long[] workSpace, int firstArrayLeft, int secondArryLeft, int secondArryRight) {
        int i = firstArrayLeft;
        int j = secondArryLeft;
        int k = 0;

        while (i <= secondArryLeft - 1 && j <= secondArryRight) {
            if (mLArray[i] < mLArray[j]) {
                workSpace[k++] = mLArray[i++];
            } else {
                workSpace[k++] = mLArray[j++];
            }
        }

        while (i <= secondArryLeft - 1) {
            workSpace[k++] = mLArray[i++];
        }

        while (j <= secondArryRight) {
            workSpace[k++] = mLArray[j++];
        }

        copyBack(workSpace, firstArrayLeft, secondArryRight);
    }

    private void copyBack(long[] workSpace, int fromIndex, int toIndex) {
        int n = toIndex - fromIndex + 1;
        for (int i = 0; i < n; i++) {
            mLArray[fromIndex + i] = workSpace[i];
        }
    }
}
